home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / unate.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  9.8 KB  |  433 lines  |  [TEXT/R*ch]
  1. /*
  2.  *  unate.c -- routines for dealing with unate functions
  3.  */
  4.  
  5. #include "espresso.h"
  6.  
  7. static pset_family abs_covered();
  8. static pset_family abs_covered_many();
  9. static int abs_select_restricted();
  10.  
  11. pcover map_cover_to_unate(T)
  12. pcube *T;
  13. {
  14.     register unsigned int word_test, word_set, bit_test, bit_set;
  15.     register pcube p, pA;
  16.     pset_family A;
  17.     pcube *T1;
  18.     int ncol, i;
  19.  
  20.     A = sf_new(CUBELISTSIZE(T), cdata.vars_unate);
  21.     A->count = CUBELISTSIZE(T);
  22.     foreachi_set(A, i, p) {
  23.     (void) set_clear(p, A->sf_size);
  24.     }
  25.     ncol = 0;
  26.  
  27.     for(i = 0; i < cube.size; i++) {
  28.     if (cdata.part_zeros[i] > 0) {
  29.         assert(ncol <= cdata.vars_unate);
  30.  
  31.         /* Copy a column from T to A */
  32.         word_test = WHICH_WORD(i);
  33.         bit_test = 1 << WHICH_BIT(i);
  34.         word_set = WHICH_WORD(ncol);
  35.         bit_set = 1 << WHICH_BIT(ncol);
  36.  
  37.         pA = A->data;
  38.         for(T1 = T+2; (p = *T1++) != 0; ) {
  39.         if ((p[word_test] & bit_test) == 0) {
  40.             pA[word_set] |= bit_set;
  41.         }
  42.         pA += A->wsize;
  43.         }
  44.  
  45.         ncol++;
  46.     }
  47.     }
  48.  
  49.     return A;
  50. }
  51.  
  52. pcover map_unate_to_cover(A)
  53. pset_family A;
  54. {
  55.     register int i, ncol, lp;
  56.     register pcube p, pB;
  57.     int var, nunate, *unate;
  58.     pcube last;
  59.     pset_family B;
  60.  
  61.     B = sf_new(A->count, cube.size);
  62.     B->count = A->count;
  63.  
  64.     /* Find the unate variables */
  65.     unate = ALLOC(int, cube.num_vars);
  66.     nunate = 0;
  67.     for(var = 0; var < cube.num_vars; var++) {
  68.     if (cdata.is_unate[var]) {
  69.         unate[nunate++] = var;
  70.     }
  71.     }
  72.  
  73.     /* Loop for each set of A */
  74.     pB = B->data;
  75.     foreach_set(A, last, p) {
  76.  
  77.     /* Initialize this set of B */
  78.     INLINEset_fill(pB, cube.size);
  79.  
  80.     /* Now loop for the unate variables; if the part is in A,
  81.      * then this variable of B should be a single 1 in the unate
  82.      * part.
  83.      */
  84.     for(ncol = 0; ncol < nunate; ncol++) {
  85.         if (is_in_set(p, ncol)) {
  86.         lp = cube.last_part[unate[ncol]];
  87.         for(i = cube.first_part[unate[ncol]]; i <= lp; i++) {
  88.             if (cdata.part_zeros[i] == 0) {
  89.             set_remove(pB, i);
  90.             }
  91.         }
  92.         }
  93.     }
  94.     pB += B->wsize;
  95.     }
  96.  
  97.     FREE(unate);
  98.     return B;
  99. }
  100.  
  101. /*
  102.  *  unate_compl
  103.  */
  104.  
  105. pset_family unate_compl(A)
  106. pset_family A;
  107. {
  108.     register pset p, last;
  109.  
  110.     /* Make sure A is single-cube containment minimal */
  111. /*    A = sf_rev_contain(A);*/
  112.  
  113.     foreach_set(A, last, p) {
  114.     PUTSIZE(p, set_ord(p));
  115.     }
  116.  
  117.     /* Recursively find the complement */
  118.     A = unate_complement(A);
  119.  
  120.     /* Now, we can guarantee a minimal result by containing the result */
  121.     A = sf_rev_contain(A);
  122.     return A;
  123. }
  124.  
  125.  
  126. /*
  127.  *  Assume SIZE(p) records the size of each set
  128.  */
  129. pset_family unate_complement(A)
  130. pset_family A;            /* disposes of A */
  131. {
  132.     pset_family Abar;
  133.     register pset p, p1, restrict;
  134.     register int i;
  135.     int max_i, min_set_ord, j;
  136.  
  137.     /* Check for no sets in the matrix -- complement is the universe */
  138.     if (A->count == 0) {
  139.     sf_free(A);
  140.     Abar = sf_new(1, A->sf_size);
  141.     (void) set_clear(GETSET(Abar, Abar->count++), A->sf_size);
  142.  
  143.     /* Check for a single set in the maxtrix -- compute de Morgan complement */
  144.     } else if (A->count == 1) {
  145.     p = A->data;
  146.     Abar = sf_new(A->sf_size, A->sf_size);
  147.     for(i = 0; i < A->sf_size; i++) {
  148.         if (is_in_set(p, i)) {
  149.         p1 = set_clear(GETSET(Abar, Abar->count++), A->sf_size);
  150.         set_insert(p1, i);
  151.         }
  152.     }
  153.     sf_free(A);
  154.  
  155.     } else {
  156.  
  157.     /* Select splitting variable as the variable which belongs to a set
  158.      * of the smallest size, and which has greatest column count
  159.      */
  160.     restrict = set_new(A->sf_size);
  161.     min_set_ord = A->sf_size + 1;
  162.     foreachi_set(A, i, p) {
  163.         if (SIZE(p) < min_set_ord) {
  164.         set_copy(restrict, p);
  165.         min_set_ord = SIZE(p);
  166.         } else if (SIZE(p) == min_set_ord) {
  167.         set_or(restrict, restrict, p);
  168.         }
  169.     }
  170.  
  171.     /* Check for no data (shouldn't happen ?) */
  172.     if (min_set_ord == 0) {
  173.         A->count = 0;
  174.         Abar = A;
  175.  
  176.     /* Check for "essential" columns */
  177.     } else if (min_set_ord == 1) {
  178.         Abar = unate_complement(abs_covered_many(A, restrict));
  179.         sf_free(A);
  180.         foreachi_set(Abar, i, p) {
  181.         set_or(p, p, restrict);
  182.         }
  183.  
  184.     /* else, recur as usual */
  185.     } else {
  186.         max_i = abs_select_restricted(A, restrict);
  187.  
  188.         /* Select those rows of A which are not covered by max_i,
  189.          * recursively find all minimal covers of these rows, and
  190.          * then add back in max_i
  191.          */
  192.         Abar = unate_complement(abs_covered(A, max_i));
  193.         foreachi_set(Abar, i, p) {
  194.         set_insert(p, max_i);
  195.         }
  196.  
  197.         /* Now recur on A with all zero's on column max_i */
  198.         foreachi_set(A, i, p) {
  199.         if (is_in_set(p, max_i)) {
  200.             set_remove(p, max_i);
  201.             j = SIZE(p) - 1;
  202.             PUTSIZE(p, j);
  203.         }
  204.         }
  205.  
  206.         Abar = sf_append(Abar, unate_complement(A));
  207.     }
  208.     set_free(restrict);
  209.     }
  210.  
  211.     return Abar;
  212. }
  213.  
  214. pset_family exact_minimum_cover(T)
  215. IN pset_family T;
  216. {
  217.     register pset p, last, p1;
  218.     register int i, n;
  219.     int lev, lvl;
  220.     pset nlast;
  221.     pset_family temp;
  222.     long start = ptime();
  223.     struct {
  224.     pset_family sf;
  225.     int level;
  226.     } stack[32];                /* 32 suffices for 2 ** 32 cubes ! */
  227.  
  228.     if (T->count <= 0)
  229.     return sf_new(1, T->sf_size);
  230.     for(n = T->count, lev = 0; n != 0; n >>= 1, lev++)   ;
  231.  
  232.     /* A simple heuristic ordering */
  233.     T = lex_sort(sf_save(T));
  234.  
  235.     /* Push a full set on the stack to get things started */
  236.     n = 1;
  237.     stack[0].sf = sf_new(1, T->sf_size);
  238.     stack[0].level = lev;
  239.     set_fill(GETSET(stack[0].sf, stack[0].sf->count++), T->sf_size);
  240.  
  241.     nlast = GETSET(T, T->count - 1);
  242.     foreach_set(T, last, p) {
  243.  
  244.     /* "unstack" the set into a family */
  245.     temp = sf_new(set_ord(p), T->sf_size);
  246.     for(i = 0; i < T->sf_size; i++)
  247.         if (is_in_set(p, i)) {
  248.         p1 = set_fill(GETSET(temp, temp->count++), T->sf_size);
  249.         set_remove(p1, i);
  250.         }
  251.     stack[n].sf = temp;
  252.     stack[n++].level = lev;
  253.  
  254.     /* Pop the stack and perform (leveled) intersections */
  255.     while (n > 1 && (stack[n-1].level==stack[n-2].level || p == nlast)) {
  256.         temp = unate_intersect(stack[n-1].sf, stack[n-2].sf, FALSE);
  257.         lvl = MIN(stack[n-1].level, stack[n-2].level) - 1;
  258.         if (debug & MINCOV && lvl < 10) {
  259.         printf("# EXACT_MINCOV[%d]: %4d = %4d x %4d, time = %s\n",
  260.             lvl, temp->count, stack[n-1].sf->count,
  261.             stack[n-2].sf->count, print_time(ptime() - start));
  262.         (void) fflush(stdout);
  263.         }
  264.         sf_free(stack[n-2].sf);
  265.         sf_free(stack[n-1].sf);
  266.         stack[n-2].sf = temp;
  267.         stack[n-2].level = lvl;
  268.         n--;
  269.     }
  270.     }
  271.  
  272.     temp = stack[0].sf;
  273.     p1 = set_fill(set_new(T->sf_size), T->sf_size);
  274.     foreach_set(temp, last, p)
  275.     INLINEset_diff(p, p1, p);
  276.     set_free(p1);
  277.     if (debug & MINCOV1) {
  278.     printf("MINCOV: family of all minimal coverings is\n");
  279.     sf_print(temp);
  280.     }
  281.     sf_free(T);         /* this is the copy of T we made ... */
  282.     return temp;
  283. }
  284.  
  285. /*
  286.  *  unate_intersect -- intersect two unate covers
  287.  *
  288.  *  If largest_only is TRUE, then only the largest cube(s) are returned
  289.  */
  290.  
  291. #define MAGIC 500               /* save 500 cubes before containment */
  292.  
  293. pset_family unate_intersect(A, B, largest_only)
  294. pset_family A, B;
  295. bool largest_only;
  296. {
  297.     register pset pi, pj, lasti, lastj, pt;
  298.     pset_family T, Tsave;
  299.     bool save;
  300.     int maxord, ord;
  301.  
  302.     /* How large should each temporary result cover be ? */
  303.     T = sf_new(MAGIC, A->sf_size);
  304.     Tsave = NULL;
  305.     maxord = 0;
  306.     pt = T->data;
  307.  
  308.     /* Form pairwise intersection of each set of A with each cube of B */
  309.     foreach_set(A, lasti, pi) {
  310.  
  311.     foreach_set(B, lastj, pj) {
  312.  
  313.         save = set_andp(pt, pi, pj);
  314.  
  315.         /* Check if we want the largest only */
  316.         if (save && largest_only) {
  317.         if ((ord = set_ord(pt)) > maxord) {
  318.             /* discard Tsave and T */
  319.             if (Tsave != NULL) {
  320.             sf_free(Tsave);
  321.             Tsave = NULL;
  322.             }
  323.             pt = T->data;
  324.             T->count = 0;
  325.             /* Re-create pt (which was just thrown away) */
  326.             (void) set_and(pt, pi, pj);
  327.             maxord = ord;
  328.         } else if (ord < maxord) {
  329.             save = FALSE;
  330.         }
  331.         }
  332.  
  333.         if (save) {
  334.         if (++T->count >= T->capacity) {
  335.             T = sf_contain(T);
  336.             Tsave = (Tsave == NULL) ? T : sf_union(Tsave, T);
  337.             T = sf_new(MAGIC, A->sf_size);
  338.             pt = T->data;
  339.         } else {
  340.             pt += T->wsize;
  341.         }
  342.         }
  343.     }
  344.     }
  345.  
  346.  
  347.     /* Contain the final result and merge it into Tsave */
  348.     T = sf_contain(T);
  349.     Tsave = (Tsave == NULL) ? T : sf_union(Tsave, T);
  350.  
  351.     return Tsave;
  352. }
  353.  
  354. /*
  355.  *  abs_covered -- after selecting a new column for the selected set,
  356.  *  create a new matrix which is only those rows which are still uncovered
  357.  */
  358. static pset_family
  359. abs_covered(A, pick)
  360. pset_family A;
  361. register int pick;
  362. {
  363.     register pset last, p, pdest;
  364.     register pset_family Aprime;
  365.  
  366.     Aprime = sf_new(A->count, A->sf_size);
  367.     pdest = Aprime->data;
  368.     foreach_set(A, last, p)
  369.     if (! is_in_set(p, pick)) {
  370.         INLINEset_copy(pdest, p);
  371.         Aprime->count++;
  372.         pdest += Aprime->wsize;
  373.     }
  374.     return Aprime;
  375. }
  376.  
  377.  
  378. /*
  379.  *  abs_covered_many -- after selecting many columns for ther selected set,
  380.  *  create a new matrix which is only those rows which are still uncovered
  381.  */
  382. static pset_family
  383. abs_covered_many(A, pick_set)
  384. pset_family A;
  385. register pset pick_set;
  386. {
  387.     register pset last, p, pdest;
  388.     register pset_family Aprime;
  389.  
  390.     Aprime = sf_new(A->count, A->sf_size);
  391.     pdest = Aprime->data;
  392.     foreach_set(A, last, p)
  393.     if (setp_disjoint(p, pick_set)) {
  394.         INLINEset_copy(pdest, p);
  395.         Aprime->count++;
  396.         pdest += Aprime->wsize;
  397.     }
  398.     return Aprime;
  399. }
  400.  
  401.  
  402. /*
  403.  *  abs_select_restricted -- select the column of maximum column count which
  404.  *  also belongs to the set "restrict"; weight each column of a set as
  405.  *  1 / (set_ord(p) - 1).
  406.  */
  407. static int
  408. abs_select_restricted(A, restrict)
  409. pset_family A;
  410. pset restrict;
  411. {
  412.     register int i, best_var, best_count, *count;
  413.  
  414.     /* Sum the elements in these columns */
  415.     count = sf_count_restricted(A, restrict);
  416.  
  417.     /* Find which variable has maximum weight */
  418.     best_var = -1;
  419.     best_count = 0;
  420.     for(i = 0; i < A->sf_size; i++) {
  421.     if (count[i] > best_count) {
  422.         best_var = i;
  423.         best_count = count[i];
  424.     }
  425.     }
  426.     FREE(count);
  427.  
  428.     if (best_var == -1)
  429.     fatal("abs_select_restricted: should not have best_var == -1");
  430.  
  431.     return best_var;
  432. }
  433.